package the.offer.Algorithm;

import the.offer.Util.SortTestHelper;

public class Sort {

    private Sort() {
    }

    /**
     * 1.选择排序
     */
    public static void selectionSort(Comparable[] arr, int n) {
        for (int i = 0; i < n; i++) {
            // 寻找[i,n) 区间里的最小值
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    /**
     * 改进的选择排序
     */
    public static void selectionSortAdvance(Comparable[] arr, int n) {
        int left = 0, right = n - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = right;

            // 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex]
            if (arr[minIndex].compareTo(arr[maxIndex]) > 0)
                swap(arr, minIndex, maxIndex);

            for (int i = left + 1; i < right; i++) {
                if (arr[i].compareTo(arr[minIndex]) < 0)
                    minIndex = i;
                else if (arr[i].compareTo(arr[maxIndex]) > 0)
                    maxIndex = i;
            }

            swap(arr, left, minIndex);
            swap(arr, right, maxIndex);

            left++;
            right--;
        }
    }

    private static void swap(Object[] arr, int i, int j) {
        Object o = arr[i];
        arr[i] = arr[j];
        arr[j] = o;
    }


    /**
     * 2. 插入排序
     */
    public static void insertionSort(Comparable[] arr, int n) {
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j].compareTo(arr[j - 1]) < 0) {
                    swap(arr, j, j - 1);
                } else
                    break;
            }
        }
    }

    /**
     * 改进的插入排序
     */
    public static void insertionSortAdvance(Comparable[] arr, int n) {
        for (int i = 1; i < n; i++) {
            Comparable o = arr[i];
            int j;
            for (j = i; j > 0 && arr[j - 1].compareTo(o) > 0; j--) {
                arr[j] = arr[j - 1]; // 以赋值替代交换，提前终止循环
            }
            arr[j] = o;
        }
    }


    /**
     * 3. 希尔排序
     */
    public static void shellSort(Comparable[] arr) {
        int n = arr.length;
        int h = 1;
        while (h < n / 3) h = 3 * h + 1;

        while (h >= 1) {
            for (int i = h; i < n; i++) {
                Comparable e = arr[i];
                int j = i;
                for (; j >= h && e.compareTo(arr[j - h]) < 0; j -= h) {
                    arr[j] = arr[j - h];
                }
                arr[j] = e;
            }
            h /= 3;
        }
    }

    /**
     * 4. 冒泡排序
     */
    public static void bubbleSort1(Comparable[] arr) {
        boolean swapped;
        int n = arr.length;
        do {
            swapped = false;
            for (int i = 1; i < n; i++) {
                if (arr[i - 1].compareTo(arr[i]) > 0) {
                    swapped = true;
                    swap(arr, i - 1, i);
                }
            }
            // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置
            // 所以下一次排序, 最后的元素可以不再考虑
            n--;
        } while (swapped);
    }

    public static void bubbleSort2(Comparable[] arr) {
        int n = arr.length;
        int newN;
        do {
            newN = 0;
            for (int i = 1; i < n; i++) {
                if (arr[i - 1].compareTo(arr[i]) > 0) {
                    swap(arr, i - 1, i);
                    newN = i;
                }
            }
            n = newN;
        } while (newN > 0);
    }


    public static void main(String[] args) {
        int n = 20;
        Integer[] array = SortTestHelper.generateRandomArray(n, 0, n);
//        selectionSort(array,n);  // 选择排序
//        selectionSortAdvance(array, n);// 优化的选择排序
//        insertionSort(array, n); // 插入排序
//        insertionSortAdvance(array, n); // 优化的插入排序
//        shellSort(array); // 希尔排序
        SortTestHelper.printArray(array);
    }
}
